package com.zx._12_算法.数据结构.link;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Demo2 合并两个两个有序链表(困难模式)
 *         已知有两个有序链表(链表元素从小到大)，请实现函数merge_link，将两个链表合并成一个有序链表，并返回新链表，原有的两个链表不要修改
 * @author: zhangxue
 * @date: 2019年7月27日下午8:34:11
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Demo2 {

    public static void main(String[] args) {
        Node<Integer> node1 = getNodes(1, 2, 3, 10, 12);
        Node<Integer> node2 = getNodes(3, 4, 5, 11, 20);

        // 确定第一个节点
        Node<Integer> nodeNew = new Node<>();

        Integer data1 = node1.data;
        Integer data2 = node2.data;
        if (data1 < data2) {
            nodeNew.data = data1;
            node1 = node1.next;
        } else {
            nodeNew.data = data2;
            node2 = node2.next;
        }

        Node<Integer> node = nodeNew;
        while (node1 != null || node2 != null) {
            Node<Integer> nextNode = new Node<>();
            // 判断最小的值是否是node1的节点
            boolean minIsNode1 = true;
            if (node1 == null) {
                minIsNode1 = false;
            } else if (node2 == null) {
                minIsNode1 = true;
            }

            // 根据上面的判断初始化nextNode节点
            if (minIsNode1) {
                nextNode.data = node1.data;
                node1 = node1.next;
            } else {
                nextNode.data = node2.data;
                node2 = node2.next;
            }

            node.next = nextNode;
            node = nextNode;
        }

        while (nodeNew != null) {
            System.out.println(nodeNew.data);
            nodeNew = nodeNew.next;
        }
    }

    public static Node<Integer> getNodes(Integer... nums) {
        Node<Integer> result = new Node<>();
        result.data = nums[0];

        Node<Integer> node = result;
        for (int i = 1; i < nums.length; i++) {
            Node<Integer> node2 = new Node<>();
            node2.data = nums[i];
            node.next = node2;
            node = node2;
        }
        return result;
    }

    static class Node<T> {

        T data;
        Node<T> next;
    }
}
